package com.zx._12_算法.剑指offer._2022;

import com.zx._12_算法.TreeNode;
import java.util.LinkedList;

/**
 * https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/
 */
public class 二叉树的深度 {


    /**
     * 动态规划
     *
     * @param root
     * @return
     */
    public int maxDepth1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int depth = 0;
        LinkedList<TreeNode> link = new LinkedList<>();
        link.offer(root);

        while (!link.isEmpty()) {
            int size = link.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode node = link.pop();
                if (node.left != null) {
                    link.offer(node.left);
                }
                if (node.right != null) {
                    link.offer(node.right);
                }
            }
        }
        return depth;
    }

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        // 分别获得左右两边各自的深度
        int d1 = maxDepth(left);
        int d2 = maxDepth(right);

        return d1 > d2 ? ++d1 : ++d2;
    }
}
